package chapter02;

public class CanJump55 {
    /**
     * 贪心算法
     * 当前位置在pos pos位置能到的最远距离为pos+nums[pos]
     * 初始化能走的最远距离mostLength==nums[0]
     * i->1~mostLength
     *    更新能走到最远距离 mostLength=max(mostLength,i+nums[i])
     *    如果nums={0} 会进不去循环 所以i从0开始 i->0~mostLength
     *    如果能走到的最远距离已经到达末尾 返回结果
     * 退出循环说明走到的最远距离不能到达末尾
     */
    public boolean canJump(int[] nums) {
        int mostLength=nums[0];
        for(int i=0;i<=mostLength;i++){
            mostLength=Math.max(mostLength,i+nums[i]);
            if(mostLength>=nums.length-1){
                return true;
            }
        }
        return false;
    }


    //深度优先遍历
    public boolean canJump1(int[] nums) {
        return process(nums,0);
    }

    public boolean process(int[] nums,int pos) {
        if(pos>=nums.length-1){
            return true;
        }
        for(int i=nums[pos];i>0;i--){
            if(process(nums,pos+i)){
                return true;
            }
        }
        return false;
    }

}
